package lbj.cyw.dp;
/*
   416. 分割等和子集

      变相的01背包问题: 数组sum/2相当于背包容量, nums[i]相当于物品重量
* */
public class CanPartition416 {
    public boolean canPartition(int[] nums) {
        if (nums.length==1){
            return false;
        }
        int sum=0;
        for (int num : nums) {
            sum+=num;
        }
        if(sum%2!=0){
            return false;
        }
        sum/=2;

        int[] dp=new int[sum+1];
        for(int i=0;i<nums.length;i++){
            for(int j=sum;j>=nums[i];j--){
                dp[j]=Math.max(dp[j],dp[i-nums[j]]+nums[j]);
            }
        }
        return dp[sum]==sum;
    }
}
